package atop;

import java.util.Arrays;
import java.util.Random;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/15 11:23
 * @描述 暂无
 */
public class 快速排序 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{0xE3, 381, 8, 6, 4, 7, 9, 3, 5, 2, 1, 782, 696, 259, 0x15};
        System.out.println("正确答案：    [1, 2, 3, 4, 5, 6, 7, 8, 9, 21, 227, 259, 381, 696, 782]");
        sortArray(nums1);
        System.out.println(Arrays.toString(nums1));
    }
    public static void quickSort1(int[] nums, int start, int end) {
        if (start >= end) return;
        int left = start, right = end, value = nums[left];
        while (left < right) {
            while (left < right && nums[right] > value) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] < value) {
                left++;
            }
            nums[right] = nums[left];
            nums[left] = value;
            quickSort1(nums, start, left - 1);
            quickSort1(nums, left + 1, end);
        }
    }


    public static int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int partition = getPartition(nums, left, right);// 分区排序一次，选取标记点，并使得标记点左侧的式子比标记数字大，右侧的数字比标记数字小
        quickSort(nums, left, partition - 1);
        quickSort(nums, partition + 1, right);
    }

    private static int getPartition(int[] nums, int left, int right) {
        int randomIndex = new Random().nextInt(right - left + 1) + left;// 从 [left,right] 中随机取一个数字，可以有效避免当数组基本有序时，快排失效
        swap(nums, randomIndex, right); // 交换 randomIndex 和 right 位置的元素，取标记点数字为 nums[right]

        int index = left;
        for (int i = left; i < right; i++) { // 找到 [left, right - 1] 中所有比 nums[right] 小的数字，并依次放置在数列左侧
            if (nums[i] < nums[right]) {
                swap(nums, i, index++);
            }
        }
        // 循环结束后， [left, index - 1] 的数字均比 nums[right] 小，
        // 且 [count, right -1] 的数字均比 nums[right] 大
        // 交换 nums[index] 和 nums[right] 即可达到目的
        swap(nums, index, right);
        // index 为标记数字的当前位置
        return index;
    }

    private static void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
